/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._687;

/**
 * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
 * <p>
 * 注意：两个节点之间的路径长度由它们之间的边数表示。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * <p>
 * 5
 * / \
 * 4   5
 * / \   \
 * 1   1   5
 * 输出:
 * <p>
 * 2
 * 示例 2:
 * <p>
 * 输入:
 * <p>
 * 1
 * / \
 * 4   5
 * / \   \
 * 4   4   5
 * 输出:
 * <p>
 * 2
 * 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._687
 * @ClassName: LongestUnivaluePath
 * @Author: linyaonan
 * @Date: 2020/1/16 14:24
 */
public class LongestUnivaluePath {
    int max;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, root.val);
        return max;
    }

    private int dfs(TreeNode node, int t) {
        if (node != null) {
            int left = dfs(node.left, node.val);
            int right = dfs(node.right, node.val);
            max = Math.max(max, left + right);
            if (node.val == t) {
                // 边长为左子树与右子树中最长的
                return Math.max(left, right) + 1;
            } else {
                // 该条边作废
                return 0;
            }
        } else {
            return 0;
        }
    }
}
